<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>1657：[Usaco2006 Mar]Mooo 奶牛的歌声</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar]Mooo 奶牛的歌声</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Usaco2006 Mar]Mooo 奶牛的歌声</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Usaco2006 Mar]Mooo 奶牛的歌声                </h1>
                <p>时间限制：5s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：64MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><p><span style="font-size: medium; ">Farmer John's N (1 &lt;= N &lt;= 50,000) cows are standing in a very straight row and mooing. Each cow has a unique height h in the range 1..2,000,000,000 nanometers (FJ really is a stickler for precision). Each cow moos at some volume v in the range 1..10,000. This &quot;moo&quot; travels across the row of cows in both directions (except for the end cows, obviously). Curiously, it is heard only by the closest cow in each direction whose height is strictly larger than that of the mooing cow (so each moo will be heard by 0, 1 or 2 other cows, depending on not whether or taller cows exist to the mooing cow's right or left).  The total moo volume heard by given cow is the sum of all the moo volumes v for all cows whose mooing reaches the cow. Since some (presumably taller) cows might be subjected to a very large moo volume, FJ wants to buy earmuffs for the cow whose hearing is most threatened. Please compute the loudest moo volume heard by any cow. </span></p>
<p></p>
<p><span style="font-size: medium; ">  Farmer John的N(1&lt;=N&lt;=50,000)头奶牛整齐地站成一列&ldquo;嚎叫&rdquo;。每头奶牛有一个确定的高度h(1&lt;=h&lt;=2000000000)，叫的音量为v (1&lt;=v&lt;=10000)。每头奶牛的叫声向两端传播，但在每个方向都只会被身高严格大于它的最近的一头奶牛听到，所以每个叫声都只会 被0，1，2头奶牛听到（这取决于它的两边有没有比它高的奶牛）。  一头奶牛听到的总音量为它听到的所有音量之和。自从一些奶牛遭受巨大的音量之后，Farmer John打算买一个耳罩给被残害得最厉 害的奶牛，请你帮他计算最大的总音量。</span></p></p><hr/><h3>输入格式</h3><p><p><span style="font-size: medium; ">* Line 1: A single integer, N. </span></p>
<p><span style="font-size: medium; "> * Lines 2..N+1: Line i+1 contains two space-separated integers, h and         v, for the cow standing at location i.</span></p>
<p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">行：一个正整数</span><span lang="EN-US">N.</span></span></p>
<p class="MsoNormal"><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">到</span><span lang="EN-US">N+1</span><span style="font-family: 宋体; ">行：每行包括</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">个用空格隔开的整数，分别代表站在队伍中第</span><span lang="EN-US">i</span><span style="font-family: 宋体; ">个位置的奶牛的身高以及她唱歌时的音量．</span></span></p>
</p></p><hr/><h3>输出格式</h3><p><p><span style="font-size: medium; ">* Line 1: The loudest moo volume heard by any single cow.</span></p>
<p><span style="font-size: medium; "><br type="_moz" />
</span></p>
<p><span style="font-size: medium; "><span lang="EN-US">&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-family: 宋体; ">队伍中的奶牛所能听到的最高的总音量．</span></span></p></p><hr/><h3>样例输入</h3><pre>3
4 2
3 5
6 10

INPUT DETAILS:

Three cows: the first one has height 4 and moos with volume 2, etc.
</pre><hr/><h3>样例输出</h3><pre>7
</pre><hr/><h3>提示</h3><p><p><span style="font-size: medium; ">&nbsp;</span><a id="fck_paste_padding"><span style="font-size: medium; ">﻿</span></a><span style="font-size: medium; "><span lang="EN-US">&nbsp; &nbsp;&nbsp;</span><span style="font-family: 宋体; ">队伍中的第</span><span lang="EN-US">3</span><span style="font-family: 宋体; ">头奶牛可以听到第</span><span lang="EN-US">1</span><span style="font-family: 宋体; ">头和第</span><span lang="EN-US">2</span><span style="font-family: 宋体; ">头奶牛的歌声，于是她能听到的总音量为</span><span lang="EN-US">2+5=7</span><span style="font-family: 宋体; ">．虽然她唱歌时的音量为</span><span lang="EN-US">10</span><span style="font-family: 宋体; ">，但并没有奶牛可以听见她的歌声．</span></span></p></p><hr/><h3>题目来源</h3><p>Silver</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=1657" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=1657" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>